/*
 * Copyright (C), 2015-2018
 * FileName: Solution049
 * Author:   zhao
 * Date:     2018/12/7 18:28
 * Description: 49. 字母异位词分组
 * History:
 * <author>          <time>          <version>          <desc>
 * 作者姓名           修改时间           版本号              描述
 */
package com.lizhaoblog.mid;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 〈一句话功能简述〉<br>
 * 〈49. 字母异位词分组〉
 *
 * @author zhao
 * @date 2018/12/7 18:28
 * @since 1.0.1
 */
public class Solution049 {
    /**************************************
     * 题目

     给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。

     示例:

     输入: ["eat", "tea", "tan", "ate", "nat", "bat"],
     输出:
     [
     ["ate","eat","tea"],
     ["nat","tan"],
     ["bat"]
     ]
     说明：

     所有输入均为小写字母。
     不考虑答案输出的顺序。
     **************************************/

    /*************************************
     想法：

     用一个hashMap<String, List<String>>来存储出现的单词

     key是单词进行排序之后的数据（比如eat、tea、ate，这些的key都是aet）

     value是数组

     我的做法
     超过97%的测试案例
     时间复杂度/空间复杂度：n/n
     代码执行过程：

     总结：

     ************************************/
    public List<List<String>> groupAnagrams(String[] strs) {
        if (strs.length == 0) {
            return Collections.emptyList();
        }

        Map<String, List<String>> ans = new HashMap<>();
        for (String str : strs) {
            char[] chars = str.toCharArray();
            Arrays.sort(chars);
            String key = String.valueOf(chars);
            if (!ans.containsKey(key)) {
                ans.put(key, new ArrayList<String>());
            }
            ans.get(key).add(str);
        }

        return new ArrayList(ans.values());
    }

    /**************************************
     * 比我好的答案 better
     * ***********************************/
    public List<List<String>> better(String[] strs) {
        if (strs.length == 0) {
            return Collections.emptyList();
        }
        Map<String, List> ans = new HashMap<String, List>();
        int[] count = new int[26];
        for (String s : strs) {
            Arrays.fill(count, 0);
            for (char c : s.toCharArray()) {
                count[c - 'a']++;
            }

            StringBuilder sb = new StringBuilder("");
            for (int i = 0; i < 26; i++) {
                sb.append('#');
                sb.append(count[i]);
            }
            String key = sb.toString();
            if (!ans.containsKey(key)) {
                ans.put(key, new ArrayList());
            }
            ans.get(key).add(s);
        }
        return new ArrayList(ans.values());
    }
}
